package n2001;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	static class TrieNode{
		boolean isStr;
		TrieNode [] next;
		public TrieNode() {
			isStr=false;
			next=new TrieNode[26];
		}
	}
	
	static TrieNode[] nodeArray=new TrieNode[20001];
	static {
		for(int i=0;i<nodeArray.length;i++)
		{
			nodeArray[i]=new TrieNode();
		}
	}
	
	static int globalCount=1;
	
	static void insert(TrieNode root,String str)
	{
		TrieNode p=root;
		for(int i=0;i<str.length();i++)
		{
			if(p.next[str.charAt(i)-'a']!=null)
			{
				p=p.next[str.charAt(i)-'a'];
				p.isStr=true;
			}else {
				p.next[str.charAt(i)-'a']=nodeArray[globalCount++];
				p=p.next[str.charAt(i)-'a'];
			}
		}
		p.isStr=true;
	}
	
	static String find(TrieNode root,String str)
	{
		TrieNode p=root;
		for(int i=0;i<str.length();i++)
		{
			if(p.next[str.charAt(i)-'a']!=null)
			{
				p=p.next[str.charAt(i)-'a'];
				if(!p.isStr) {
					p.isStr=true;
					return str.substring(0,i+1);
				}
			}
		}
		return str;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub

		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		
		String line=null;
		
		String[] input=new String[1001];
		
		int count=0;
		
		while((line=bf.readLine())!=null)
		{
			if(line.trim().equals(""))break;
			input[count++]=line;
			insert(nodeArray[0], line);
		}
		
		for(int i=0;i<count;i++)
		{
			System.out.println(input[i]+" "+find(nodeArray[0],input[i]));
		}
	}

}
